package myStack;

import java.util.*;

/**
 * 功能描述: 从栈中获取最小值 使得 pop, push , getMin 都是 O(1)
 * 2024/05/22
 * <p>
 * ZhangYi
 */
public class GetMinFromStackUtils<T> {
    private Stack<T> stack; // 栈
    private Stack<T> minStack; // 最小栈,只存放最小的元素

    Comparator<? super T> comparator ;

    public GetMinFromStackUtils(Comparator<? super T> comparator) {
        this.stack = new Stack<>();
        this.minStack = new Stack<>();
        this.comparator = comparator;
    }

    public void push(T val){
        // 两个栈都为空的情况下
        if (isEmpty()){
            // 两个栈同时压入
            stack.push(val);
            minStack.push(val);
        }else {
            if (!stack.isEmpty()){
                if (this.comparator.compare(val, minStack.peek())<0){
                    minStack.push(val);
                    stack.push(val);
                }else {
                    stack.push(val);
                }
            }
        }
    }

    public T pop(){
        if (!stack.isEmpty()){
            T pop = stack.pop();
            // 如果弹出的元素和最小栈的栈顶元素相等
            // 则最小栈弹出,保证两个栈的数据是同步的
            if (!minStack.isEmpty() && this.comparator.compare(pop, minStack.peek())==0){
                System.out.println("删除最小值"+minStack.pop());
            }
            return pop;
        }
        return null;
    }

    public T getMin(){
        if (!minStack.isEmpty()){
            return minStack.peek();
        }
        return null;
    }
    public boolean isEmpty(){
        return stack.isEmpty() && minStack.isEmpty();
    }


    public static void main(String[] args) {
        GetMinFromStackUtils<Integer> getMinFromStackUtils = new GetMinFromStackUtils<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1,
                               Integer o2) {
                return o1-o2;
            }
        });

        List<Integer> list= Arrays.asList(8, 2, 3);
        for (Integer integer : list) {
            getMinFromStackUtils.push(integer);
        }
        System.out.println(getMinFromStackUtils.getMin());

        for (int i = 0; i < list.size(); i++) {
            Integer pop = getMinFromStackUtils.pop();
        }

        System.out.println("测试完毕");
    }
}
